Stupid sort
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7b/Bogo_sort_animation.gif/220px-Bogo_sort_animation.gif)
Stupid Sort, en inglés también conocido como BogoSort[1][2] (o como slowsort[3][4]), es un algoritmo de ordenamiento particularmente inefectivo basado en el paradigma de ensayo y error. No es útil para ordenar, pero puede ser utilizado con propósitos educativos para contrastarlo con algoritmos más efectivos. También ha sido usado como ejemplo en programación lógica.[2][3][4]
Si stupid sort fuera utilizado para ordenar un mazo de cartas, consistiría en verificar primero si el mazo está en orden, y si no lo está, entonces deberíamos mezclar las cartas de forma aleatoria, verificar de nuevo si están ordenadas y así sucesivamente hasta que por una mezcla al azar encontremos el mazo ordenado. El nombre bogosort proviene de la palabra bogus.[5]
Complejidad y finalización
[editar]Este algoritmo de ordenamiento es probabilístico por naturaleza. Si se aplica a un arreglo donde todos los elementos son distintos, el número esperado de comparaciones es asintóticamente equivalente a , y el número esperado de intercambios (swaps) en el caso promedio es igual a .
En el peor caso el número de comparaciones e intercambios no está acotada. Es decir, no hay certeza de que el algoritmo termine. El mejor caso es cuando la lista original está ordenada, entonces se realizan comparaciones y ningún intercambio.
Véase también
[editar]Referencias
[editar]- ↑ Gruber, H.; Holzer, M.; Ruepp, O., «Sorting the slow way: an analysis of perversely awful randomized sorting algorithms», 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, Springer-Verlag, pp. 183-197, doi:10.1007/978-3-540-72914-3_17..
- ↑ a b Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P.; Sabry, Amr (2005), «Backtracking, interleaving, and terminating monad transformers: (functional pearl)», Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05), SIGPLAN Notices, pp. 192-203, doi:10.1145/1086365.1086390, archivado desde el original el 26 de marzo de 2012, consultado el 2 de agosto de 2013.
- ↑ a b Naish, Lee (1986), «Negation and quantifiers in NU-Prolog», Proceedings of the Third International Conference on Logic Programming, Lecture Notes in Computer Science 225, Springer-Verlag, pp. 624-634, doi:10.1007/3-540-16492-8_111..
- ↑ a b Naish, Lee (June 1995), Pruning in logic programming, Tech. Report 95/16, Melbourne, Australia: Department of Computer Science, University of Melbourne..
- ↑ «Bogosort». The Jargon File 4.4.8. 2003. Consultado el 11 de abril de 2013.